package a_erfenchazhao;

/**
 * @ClassName PingHengXieFa
 * @Description
 * @Author Zhang Li Tao
 * @Date 2024/3/16
 * @Version 1.0
 **/
public class C_PingHengXieFa {
    public static void main(String[] args) {
        int[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8};
        int target = 5;

        int leftIndex = 0; // 左边界从头开始 表示左边界肯定参与查找
        int rightIndex = array.length; // 右边界不参与查找

        // 左右边界待查找范围之中仅剩下左边界上一个元素为止 左边界是参与查找的
        while (1 < rightIndex - leftIndex) {
            int middleIndex = (leftIndex + rightIndex) >>> 1;

            // 既然是平衡查找 判断条件肯定只能有if和else两个分支
            if (target < array[middleIndex]) { // 左半部分
                rightIndex = middleIndex; // 不能减1 是因为右边界不参与查找
            } else { // 右半部分或者刚好中间索引就是目标值 但是为了平衡不能终止程序
                leftIndex = middleIndex; // 不能加1 是因为左边界参与查找
            }
        }

        // 最终待查找范围中只剩下左边界一个元素 此时判断是否就是目标值
        if (array[leftIndex] == target) {
            System.out.println(leftIndex);
            return;
        }

        System.out.println(-1);
    }
}
